/*
 * @lc app=leetcode.cn id=105 lang=typescript
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

//  思路：递归
//  通过前序遍历首位构建根节点，再通过中序遍历分割确定左右子树
//  根据左右子树不同的数量分割左右子树的前序遍历，再递归

//  复杂度：O(n) O(n)

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (!preorder.length) return null
    const root = new TreeNode(preorder[0])
    const index = inorder.indexOf(preorder[0])
    const preLeft = preorder.slice(1, index + 1), preRight = preorder.slice(index + 1)
    const inLeft = inorder.slice(0, index), inRight = inorder.slice(index + 1)
    root.left = buildTree(preLeft, inLeft)
    root.right = buildTree(preRight, inRight)
    return root
};
// @lc code=end

import { TreeNode } from "./type"
const preorder = [3, 9, 20, 15, 7]
const inorder = [9, 3, 15, 20, 7]
console.log(TreeNode.printTree(buildTree(preorder, inorder)))
